package 非比较排序;
public class RadixSort {
    public static void sort(int[] arr){
        //找到最大值的位数
        int max=Integer.MIN_VALUE;
        for (int num:arr) max=Math.max(num,max);

        //创建好桶，以及记录桶的有效值的一维数组
        int[][] bucket=new int[10][arr.length];
        int[] bucketCount=new int[10];

        // ①按照位数值的大小，放入到对应的桶中
        // ②将放好的值取出并放入到原来的数组中
        int maxLength=Integer.toString(max).length();
        for (int i = 0,n=1; i < maxLength; i++,n*=10) {
            for (int j = 0; j < arr.length; j++) {
                int s=arr[j]/n%10;
                bucket[s][bucketCount[s]++]=arr[j];
            }
            int index=0;
            for (int k = 0; k < bucketCount.length; k++) {
                if(bucketCount[k]!=0){
                    //如果记录的不为空，证明对应的桶中有数据
                    for (int l = 0; l < bucketCount[k]; l++) {
                        arr[index++]=bucket[k][l];//将放好的值取出并放入到原来的数组中
                    }
                }
                bucketCount[k]=0; //将桶中的数放回到原来的数组中后，把记录的有效数值清空
            }
        }
    }
}
